import { BSTree } from "./00_二叉搜索树BSTree";
import { AVLTreeNode } from "./04_封装AVLTheeNode(左旋转操作)";

class AVLTree<T> extends BSTree<T> {
  /**
   * rebalance: 再平衡树结构
   * @param root 不平衡的根节点
   */
  rebalance(root: AVLTreeNode<T>) {
    const pivot = root.getHigherChild; // 获取更高的子节点
    const current = pivot?.getHigherChild; // 获取更高的子节点的更高的子节点

    let resultNode: AVLTreeNode<T> | null = null;
    if (pivot?.isLeft) {
      if (current?.isLeft) {
        // 左左情况
        resultNode = root.rightRotation();
      } else {
        // 右左情况
        pivot.leftRotation();
        resultNode = root.rightRotation();
      }
    } else {
      if (current?.isRight) {
        // 右右情况
        resultNode = root.leftRotation();
      } else {
        // 左右情况
        pivot?.rightRotation();
        resultNode = root.leftRotation();
      }
    }

    // 如果pivot的current为null，则说明是根节点，让root指向resultNode
    if (!pivot?.parent) {
      this.root = resultNode;
    }
  }
}

const avlTree = new AVLTree<number>();
avlTree.insert(10);
avlTree.insert(8);
avlTree.insert(15);
avlTree.insert(7);
avlTree.insert(18);

avlTree.print();

export {};
